package tree;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/7fyw1e/
public class 子结构判断 {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    class Solution {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(A == null || B == null)
                return false;
            else
                return (recur(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B));
        }
        boolean recur(TreeNode A, TreeNode B) {
            if(B == null) return true;
            if(A == null || A.val != B.val) return false;
            return recur(A.left,B.left) && recur(A.right,B.right);
        }
    }
    class Solution2 {
        /**
         java 、 前序遍历、树遍历匹配。
         时间O(MN), M是A树的前序遍历，N是对A的子树和B树的遍历。
         空间O(M), 递归深度最大为树的结点数
         思路：对A前序遍历并在遍历过程中对A子树进行与B树的匹配。
         */
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            // 可行性剪枝
            if (B == null || A == null) return false;
            boolean res = false;
            // 前序遍历,并判断当前位置是否找到子结构。（且找到子结构就立即返回 -> 等价于下面的写法)
            res = res || recur(A,B);
            res = res || isSubStructure(A.left,B) || isSubStructure(A.right,B);
            return res;
        }

        public boolean recur(TreeNode A,TreeNode B){
            // recur函数解决的问题：根为A和根为B的树的相同方式的遍历是否一致的问题。
            // 递归边界返回 // 注意：约定空树不是任意一个树的子结构，而这里的含义是B树递归遍历完成。
            if (B == null) return true;
            // 可行性剪枝
            if (A == null && B != null) return false;
            if (A.val != B.val) return false;
            // 下一步递归。 注意：完全匹配，故使用&&
            boolean res = recur(A.left,B.left) && recur(A.right,B.right);
            // 递归返回
            return res;
        }

    }
}
